#include "BTreeNode.h"
#include <iostream>

//#define MIN(X,Y) ((X) < (Y) ? : (X) : (Y))
//#define MAX(X,Y) ((X) > (Y) ? : (X) : (Y))

using namespace std;

BTLeafNode::BTLeafNode(){	
	memset(buffer, 0, PageFile::PAGE_SIZE);
}
/* 
* Read the content of the node from the page pid in the PageFile pf. 
* @param pid[IN] the PageId to read 
* @param pf[IN] PageFile to read from 
* @return 0 if successful. Return an error code if there is an error. 
*/ 

RC BTLeafNode::read(PageId pid, const PageFile& pf){	
	memset(buffer, 0, PageFile::PAGE_SIZE);	
	return pf.read(pid, buffer);
}    
/* 
* Write the content of the node to the page pid in the PageFile pf. 
* @param pid[IN] the PageId to write to 
* @param pf[IN] PageFile to write to 
* @return 0 if successful. Return an error code if there is an error. 
*/

RC BTLeafNode::write(PageId pid, PageFile& pf){	
	return pf.write(pid, buffer);
}

/* 
* Return the number of keys stored in the node. 
* @return the number of keys in the node 
*/
int BTLeafNode::getKeyCount(){	
	int count = 0;	
	memcpy(&count, &buffer, sizeof(int));	
	return count;
}

/* 
* Insert a (key, rid) pair to the node. 
* @param key[IN] the key to insert 
* @param rid[IN] the RecordId to insert 
* @return 0 if successful. Return an error code if the node is full. 
*/
RC BTLeafNode::insert(int key, const RecordId& rid){	
	int slotSize = sizeof(RecordId) + sizeof(int);	
	int totalSize = getKeyCount() * slotSize;	
	
	//the 1st 4 bits is number of key; the 2nd 4 bits is addr of parent
	//the 3rd 4 bits is leave flag: 1 if leave and 0 if else
	//the 4th 4 bits is ptr to the sibling
	if(totalSize >= PageFile::PAGE_SIZE - 4*sizeof(int)) {
	//cout << "GetKeyCount()= "<<getKeyCount()<<"slotSize = "<<slotSize<<"Leaf node full" << endl;		
	return RC_NODE_FULL;	}

	/*if(getKeyCount() >= 84) {		
		cout << "Leaf node full" << endl;		
		return RC_NODE_FULL;	
	}*/	

	char* ptr = &(buffer[0]);	
	int i = 0;	
	ptr += sizeof(int);	
	ptr += sizeof(PageId);	
	int currKey;	
	while (ptr) {		
		memcpy(&currKey, ptr, sizeof(int));		
		if(currKey == 0) {			
			break;		
		}		
		if (currKey < key) {			
			ptr += slotSize;			
			i++;		
		} 
		else {			
			break;		
		}	
	}	

	if (&(buffer[PageFile::PAGE_SIZE]) - ptr < 20) {			
		return RC_NODE_FULL;	
	}	

	char* temp = (char*)malloc(PageFile::PAGE_SIZE * sizeof(char));	
	memset(temp, 0, PageFile::PAGE_SIZE);	
	if(totalSize > 0 && currKey != 0) {		
		memcpy(temp, ptr, totalSize - (slotSize * i));		
		memset(ptr, 0, totalSize - (slotSize * i));	
	}	

	memcpy(ptr, &key, sizeof(int));	
	ptr += sizeof(int);	
	memcpy(ptr, &rid, sizeof(RecordId));

	ptr += sizeof(RecordId);	
	if(totalSize > 0 && currKey != 0) {		
		memcpy(ptr, temp, totalSize - (slotSize * i));	
	}
	//cout << "In BTreeNode: Key = "<<key << endl;		
	free(temp);	

	int currKeyCount = getKeyCount();	
	currKeyCount++;	
	ptr = &(buffer[0]);	
	memcpy(ptr, &currKeyCount, sizeof(int));	
	return 0;
}

/* 
* Insert the (key, rid) pair to the node 
* and split the node half and half with sibling. 
* The first key of the sibling node is returned in siblingKey. 
* @param key[IN] the key to insert. 
* @param rid[IN] the RecordId to insert. 
* @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called. 
* @param siblingKey[OUT] the first key in the sibling node after split. 
* @return 0 if successful. Return an error code if there is an error. 
*/
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, BTLeafNode& sibling, int& siblingKey){	
	int slotSize = sizeof(RecordId) + sizeof(int);	
	int totalSize = getKeyCount() * slotSize;	
	int i = 0;	
	int retval = 0;	
	char* ptr = &(buffer[0]);

	ptr += sizeof(int);		// Offset the 1st four bytes	
	ptr += sizeof(PageId);	
	while(i < (getKeyCount() / 2)) {		
		ptr += slotSize;		
		i++;	
	}

	char* temp = (char*)malloc(1024*sizeof(char));	
	char* head = temp;	
	
	memset(temp, 0, 1024*sizeof(char));	
	memcpy(temp, ptr, totalSize - (slotSize * (getKeyCount()/2)));

	memset(ptr, 0, totalSize - (slotSize * (getKeyCount()/2)));	
	int newKey = getKeyCount() / 2;	
	memcpy(buffer, &newKey, sizeof(int));

	while(temp) {		
		int k;		
		RecordId r;		
		memcpy(&k, temp, sizeof(int));		
		if(k == 0) {	break;	}	

		temp += sizeof(int);		
		memcpy(&r, temp, sizeof(RecordId));		
		temp += sizeof(RecordId);		
		if(r.sid == 0 && r.pid == 0 && k != 272) {			
			int q = r.sid;			
			cout << "rid error!" << endl;		
		}		
		if( sibling.insert(k, r) != 0 ) {			
			free(head);			
			return RC_FILE_WRITE_FAILED;		
		}	
	}	
	free(head);	

	RecordId r;	
	if( sibling.readEntry(0, siblingKey, r) != 0) {		return RC_FILE_READ_FAILED;	}	
	if(key < siblingKey) {		
		if( insert(key, rid) != 0 ) {	return RC_FILE_WRITE_FAILED;	}	
	} 
	else {		
		if( sibling.insert(key, rid) != 0 ) {	return RC_FILE_WRITE_FAILED;	}	
	}	
	if( sibling.readEntry(0, siblingKey, r) != 0) {		return RC_FILE_READ_FAILED;	}	
	return retval; 
}

/* 
* Find the entry whose key value is larger than or equal to searchKey 
* and output the eid (entry number) whose key value >= searchKey. 
* Remeber that all keys inside a B+tree node should be kept sorted. 
* @param searchKey[IN] the key to search for 
* @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey 
* @return 0 if successful. Return an error code if there is an error. 
*/
RC BTLeafNode::locate(int searchKey, int& eid){ 	
	int slotSize = sizeof(RecordId) + sizeof(int);	
	int totalSize = getKeyCount() * slotSize;	
	char* ptr = &(buffer[0]);	
	int curr_key;	int i = 0;	
	ptr += sizeof(int);	
	while(ptr) {		
		memcpy(&curr_key, ptr, sizeof(int));		
		if(curr_key >= searchKey || curr_key == 0) {			
			eid = i;			
			break;		
		}		
		i++;		
		ptr += slotSize;	
	}	
	return 0; 
}

/* 
* Read the (key, rid) pair from the eid entry. 
* @param eid[IN] the entry number to read the (key, rid) pair from 
* @param key[OUT] the key from the entry 
* @param rid[OUT] the RecordId from the entry 
* @return 0 if successful. Return an error code if there is an error. 
*/
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid){ 	
	int slotSize = sizeof(RecordId) + sizeof(int);	
	int totalSize = getKeyCount() * slotSize;	
	char* ptr = &(buffer[0]);	int i = 0;	
	ptr += sizeof(int);	
	ptr += sizeof(PageId);	
	while(ptr && i < eid) {		
		ptr += slotSize;		
		i++;	
	}	
	memcpy(&key, ptr, sizeof(int));	
	ptr += sizeof(int);	
	memcpy(&rid, ptr, sizeof(RecordId));	
	return 0; 
}

/* 
* Return the pid of the next slibling node. 
* @return the PageId of the next sibling node  
*/
PageId BTLeafNode::getNextNodePtr(){ 	
	PageId pid;	
	char* ptr = &(buffer[0]);	
	ptr += sizeof(int);	
	memcpy(&pid, ptr, sizeof(PageId));	
	return pid; 
}

/* 
* Set the pid of the next slibling node. 
* @param pid[IN] the PageId of the next sibling node  
* @return 0 if successful. Return an error code if there is an error. 
*/
RC BTLeafNode::setNextNodePtr(PageId pid){ 	
	char* ptr = &(buffer[0]);	
	ptr += sizeof(int);	
	memcpy(ptr, &pid, sizeof(PageId));	
	return 0; 
}

BTNonLeafNode::BTNonLeafNode() {	
	memset(buffer, 0, PageFile::PAGE_SIZE);
}

/* 
* Read the content of the node from the page pid in the PageFile pf. 
* @param pid[IN] the PageId to read 
* @param pf[IN] PageFile to read from 
* @return 0 if successful. Return an error code if there is an error. 
*/

RC BTNonLeafNode::read(PageId pid, const PageFile& pf){	
	return pf.read(pid, buffer); 
}  

/* 
* Write the content of the node to the page pid in the PageFile pf. 
* @param pid[IN] the PageId to write to 
* @param pf[IN] PageFile to write to 
* @return 0 if successful. Return an error code if there is an error. 
*/
RC BTNonLeafNode::write(PageId pid, PageFile& pf){	
	return pf.write(pid, buffer);
}

/* 
* Return the number of keys stored in the node. 
* @return the number of keys in the node 
*/
int BTNonLeafNode::getKeyCount(){	
	int retval = 0;		
	memcpy(&retval, &buffer, sizeof(int));	
	return retval;
}

/* 
* Insert a (key, pid) pair to the node. 
* @param key[IN] the key to insert 
* @param pid[IN] the PageId to insert 
* @return 0 if successful. Return an error code if the node is full. 
*/
RC BTNonLeafNode::insert(int key, PageId pid){ 		
	int slotSize = sizeof(PageId) + sizeof(int);	
	int totalSize = getKeyCount() * slotSize;	char* ptr = &(buffer[0]);	
	int i = 0;	
	if(totalSize >= PageFile::PAGE_SIZE - slotSize) {		
		cout << "Non-leaf node is full" << endl;		
		return RC_NODE_FULL;	
	}	

	ptr += sizeof(int);	
	ptr += sizeof(PageId);	
	int currKey;	
	while (ptr) {		
		memcpy(&currKey, ptr, sizeof(int));		
		if(currKey == 0) {	break;}		
		if (currKey < key) {			
			ptr += slotSize;			
			i++;		
		} 
		else 	break;		
			
	}	
	if(currKey == key) {				
		ptr += sizeof(int);		
		memcpy(ptr, &pid, sizeof(PageId));		
		return 0;	
	}	
	if (ptr == &(buffer[PageFile::PAGE_SIZE]))		
		return RC_FILE_WRITE_FAILED;

	char* temp = (char*) malloc(PageFile::PAGE_SIZE * sizeof(char));	
	memset(temp, 0, PageFile::PAGE_SIZE);	

	if(totalSize > 0 && currKey != 0) {		
		memcpy(temp, ptr, totalSize - (slotSize * i));		
		memset(ptr, 0, totalSize - (slotSize * i));	
	}	
	memcpy(ptr, &key, sizeof(int));	
	ptr += sizeof(int);	
	memcpy(ptr, &pid, sizeof(PageId));	
	ptr += sizeof(PageId);	
	if(totalSize > 0 && currKey != 0) {		
		memcpy(ptr, temp, totalSize - (slotSize * i));	
	}	
	free(temp);	
	//set the new key count	
	int currKeyCount = getKeyCount();	
	currKeyCount++;	
	ptr = &(buffer[0]);	
	memcpy(ptr, &currKeyCount, sizeof(int));	
	return 0;
}

/* 
* Insert the (key, pid) pair to the node 
* and split the node half and half with sibling. 
* The middle key after the split is returned in midKey. 
* @param key[IN] the key to insert 
* @param pid[IN] the PageId to insert 
* @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called. * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node. 
* @return 0 if successful. Return an error code if there is an error. 
*/
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey){ 	
	int slotSize = sizeof(PageId) + sizeof(int);	
	int totalSize = getKeyCount() * slotSize;	int i = 0;	
	char* ptr = &(buffer[0]);	
	ptr += sizeof(int);	
	while(i < (getKeyCount() / 2)) {		
		ptr += slotSize;		
		i++;	
	}	
	char* temp = (char*) malloc(PageFile::PAGE_SIZE * sizeof(char));	
	char* head = temp;	
	
	memset(temp, 0, 1024*sizeof(char));	
	memcpy(temp, ptr, totalSize - (slotSize * (getKeyCount() / 2)));

	memset(ptr, 0, totalSize - (slotSize * (getKeyCount() / 2)));	
	int newKey = getKeyCount() / 2;	
	memcpy(buffer, &newKey, sizeof(int));

	while(temp) {		
		int k;		
		PageId p;		
		memcpy(&k, temp, sizeof(int));		
		if(k == 0) 		break;				
		temp += sizeof(int);		
		memcpy(&p, temp, sizeof(PageId));		
		temp += sizeof(PageId);		
		if( sibling.insert(k, p) != 0) {			
			free(head);			
			return RC_FILE_WRITE_FAILED;		
		}	
	}	
	free(head);	

	if(key < midKey) {		
		if( insert(key, pid) != 0 )			{	return RC_FILE_WRITE_FAILED;	}	
	} 
	else {		
		if( sibling.insert(key, pid) != 0 ) {	return RC_FILE_WRITE_FAILED;	}	
	}	
	return 0; 
}

/* 
* Given the searchKey, find the child-node pointer to follow and 
* output it in pid. * @param searchKey[IN] the searchKey that is being looked up. 
* @param pid[OUT] the pointer to the child node to follow. 
* @return 0 if successful. Return an error code if there is an error. 
*/
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid){	
	int slotSize = sizeof(PageId) + sizeof(int);	
	int totalSize = getKeyCount() * slotSize;	
	char* ptr = &(buffer[0]);	
	int curr_key;	
	ptr += sizeof(int);	
	ptr += sizeof(int);	
	while(ptr) {		
		memcpy(&curr_key, ptr, sizeof(int));		
		if(curr_key != 0 && curr_key < searchKey) {			
			ptr += sizeof(int);			
			//memcpy(&pid, ptr, sizeof(PageId));			
			//break;		
		} 
		else {			
			ptr -= sizeof(PageId);			
			memcpy(&pid, ptr, sizeof(PageId));			
			break;		
		}		
		ptr += slotSize;	
	} 	
	return 0;	
}

/* 
* Initialize the root node with (pid1, key, pid2). 
* @param pid1[IN] the first PageId to insert 
* @param key[IN] the key that should be inserted between the two PageIds 
* @param pid2[IN] the PageId to insert behind the key 
* @return 0 if successful. Return an error code if there is an error. 
*/
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2){	
	char* ptr = &(buffer[0]);	
	int k = 1;	
	ptr += sizeof(int);	
	memcpy(ptr, &pid1, sizeof(PageId));	
	ptr += sizeof(PageId);	
	memcpy(ptr, &key, sizeof(int));	
	ptr += sizeof(int);	
	memcpy(ptr, &pid2, sizeof(PageId));	
	memcpy(buffer, &k, sizeof(int));	
	return 0; 
}
